/**
 * \file ArbreAVL.inl
 *  
 * \author ALGRIN Thibaut
 * \author CARRE Emmanuel
 * 
 * \version 0.1
 * \date Décembre 2011
 */

using namespace tp3;

/**
 * \fn	ArbreAVL<typeCle, TypeValeur>::ArbreAVL()
 */
template<typename TypeCle, typename TypeValeur>
ArbreAVL<TypeCle, TypeValeur>::ArbreAVL()
{
	this->racine = NULL;
	this->cpt = 0;
}

/**
 * \fn	ArbreAVL<TypeCle, TypeValeur>::ArbreAVL(const ArbreAVL<TypeCle, TypeValeur>& source)	throw(std::bad_alloc)
 */
template<typename TypeCle, typename TypeValeur>
ArbreAVL<TypeCle, TypeValeur>::ArbreAVL(const ArbreAVL<TypeCle, TypeValeur>& source)		throw(std::bad_alloc)
{
	*this = source;
}

/**
 * \fn	ArbreAVL<TypeCle, TypeValeur>::~ArbreAVL()
 */
template<typename TypeCle, typename TypeValeur>
ArbreAVL<TypeCle, TypeValeur>::~ArbreAVL()
{
}

/**
 * \fn	void	ArbreAVL<TypeCle, TypeValeur>::inserer(const TypeCle& cle, const TypeValeur& valeur)
 * \param[in]	cle		Clé de l'élément à insérer.
 * \param[in]	valeur	Valeur de l'élément à insérer
 */
template<typename TypeCle, typename TypeValeur>
void	ArbreAVL<TypeCle, TypeValeur>::inserer(const TypeCle& cle, const TypeValeur& valeur)
{
	_auxInsererAVL(racine, cle, valeur);
}

/**
 * \fn	TypeValeur	ArbreAVL<TypeCle, TypeValeur>::valeur(const TypeCle& cle) const
 * \param[in]	cle	Clé de l'élément dont on chercher la valeur
 * 
 * \return	L'élement correspondant à la clé
 */
template<typename TypeCle, typename TypeValeur>
TypeValeur	ArbreAVL<TypeCle, TypeValeur>::valeur(const TypeCle& cle) const
{
	Noeud         *tmp;

	if ((tmp = _auxAppartient(this->racine, cle)) != NULL)
		return tmp->valeur;
	throw std::logic_error("La clé n'existe pas");
}

/**
 * \fn	void	ArbreAVL<TypeCle, TypeValeur>::enlever(const TypeCle& cle)	throw(std::logic_error)
 * \param[in]	cle	Clé de l'élément à enlever.
 */
template<typename TypeCle, typename TypeValeur>
void	ArbreAVL<TypeCle, TypeValeur>::enlever(const TypeCle& cle)	throw(std::logic_error)
{
	if( racine == 0 )
		throw std::logic_error("enlever: l'arbre est vide\n");
	if( _auxAppartient(racine, cle) == 0 )
		throw std::logic_error("enlever: l'element ne fait pas partie de l'arbre\n");
	_auxEnleverAVL(racine, cle);
}

/**
 * \fn	bool ArbreAVL<TypeCle, TypeValeur>::estVide() const
 * 
 * \return	Vrai si l'arbre est vide, sinon faux
 */
template<typename TypeCle, typename TypeValeur>
bool ArbreAVL<TypeCle, TypeValeur>::estVide() const
{
	if (this->racine == NULL)
		return (true);
	return (false);
}

/**
 * \fn	long ArbreAVL<TypeCle, TypeValeur>::taille() const
 * 
 * \return La taille de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
long ArbreAVL<TypeCle, TypeValeur>::taille() const
{
	return this->cpt;
}

/**
 * \fn	int ArbreAVL<TypeCle, TypeValeur>::hauteur() const	throw(std::logic_error)
 * 
 * \return La hauteur de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
int ArbreAVL<TypeCle, TypeValeur>::hauteur() const	throw(std::logic_error)
{
	if (this->racine == NULL)
		throw std::logic_error("L'arbre est vide");
	return this->_hauteur(this->racine);
}

/**
 * \fn	std::pair<TypeCle, TypeValeur> ArbreAVL<TypeCle, TypeValeur>::parent(const TypeCle&)
 * \param[in]	cle	La clé de l'élément dont on souhaite trouver le parent
 * 
 * \return La pair contenant la clé et la valeur du parent
 */
template<typename TypeCle, typename TypeValeur>
std::pair<TypeCle, TypeValeur> ArbreAVL<TypeCle, TypeValeur>::parent(const TypeCle& cle)	throw(std::logic_error)
{

	Noeud* noeudDeEl = _auxAppartient(this->racine, cle);
	Noeud* parentDeEl = _parent(this->racine, noeudDeEl);
	std::pair<TypeCle, TypeValeur>        tmp(parentDeEl->cle, parentDeEl->valeur);
	return tmp;
}

/**
 * \fn	std::pair<TypeCle, TypeValeur> ArbreAVL<TypeCle, TypeValeur>::successeur(const TypeCle&)	throw(std::logic_error)
 * \param[in]	cle	La clé de l'élément dont on cherche le successeur.
 * 
 * \return	La pair contant la clé et la valeur du successeur
 */
template<typename TypeCle, typename TypeValeur>
std::pair<TypeCle, TypeValeur> ArbreAVL<TypeCle, TypeValeur>::successeur(const TypeCle& cle)	throw(std::logic_error)
{
	return (_successeur(this->racine, cle));
}

/**
 * \fn	std::vector<std::pair<TypeCle, TypeValeur> > ArbreAVL<TypeCle, TypeValeur>::lister() const	throw(std::bad_alloc)
 * 
 * \return	Le vector contenant les pairs contenant la clé et la valeur de chaque élément de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
std::vector<std::pair<TypeCle, TypeValeur> > ArbreAVL<TypeCle, TypeValeur>::lister() const	throw(std::bad_alloc)
{
	std::vector<std::pair<TypeCle, TypeValeur> >   list;

	this->_auxEnOrdre(this->racine, list);
	return list;
}

/**
 * \fn	std::vector<std::pair<TypeCle, TypeValeur> > ArbreAVL<TypeCle, TypeValeur>::listerPreOrdre() const	throw(std::bad_alloc)
 * 
 * \return	Le vector contenant les pairs contenant la clé et la valeur de chaque élément de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
std::vector<std::pair<TypeCle, TypeValeur> > ArbreAVL<TypeCle, TypeValeur>::listerPreOrdre() const	throw(std::bad_alloc)
{
	std::vector<std::pair<TypeCle, TypeValeur> >   list;

	this->_auxPreOrdre(this->racine, list);
	return list;
}

/**
 * \fn	bool ArbreAVL<TypeCle, TypeValeur>::appartient(const TypeCle &) const
 * \param[in]	cle	La clé	de l'élément que l'on cherche
 * 
 * \return Vrai si la clé est présente dans l'arbre, sinon faux
 */
template<typename TypeCle, typename TypeValeur>
bool ArbreAVL<TypeCle, TypeValeur>::appartient(const TypeCle &cle) const
{
	if (this->_auxAppartient(this->racine->gauche, cle) != NULL)
		return true;
	if (this->_auxAppartient(this->racine->droite, cle) != NULL)
		return true;
	return false;
}

/**
 * \fn	ArbreAVL<TypeCle, TypeValeur>& ArbreAVL<TypeCle, TypeValeur>::operator=(const ArbreAVL<TypeCle, TypeValeur> & a)	throw(std::bad_alloc)
 * \param[in]	a	L'arbre de référence pour la copie.
 * 
 * \return La référence sur la copie
 */
template<typename TypeCle, typename TypeValeur>
ArbreAVL<TypeCle, TypeValeur>& ArbreAVL<TypeCle, TypeValeur>::operator=(const ArbreAVL<TypeCle, TypeValeur> & a)	throw(std::bad_alloc)
{
	this->_auxCopier(a.racine, racine);
	this->cpt = a.cpt;
	return (*this);
}

/**
 * \fn	bool ArbreAVL<TypeCle, TypeValeur>operator==(const ArbreAVL<TypeCle, TypeValeur> &a) const
 * \param[in]	a	Arbre à comparer
 * 
 * \return	Vrai si l'arbre est identique, sinon faux
 */
template<typename TypeCle, typename TypeValeur>
bool ArbreAVL<TypeCle, TypeValeur>::operator==(const ArbreAVL<TypeCle, TypeValeur> &a) const
{
	if (this->cpt != a.cpt)
		return false;
	if (this->racine->operator ==(a.racine))
		return true;
	return false;
}

/**
 * \fn	void	ArbreAVL<TypeCle, TypeValeur>::_auxInsererAVL(Noeud *&elem, const TypeValeur &val)	throw(std::bad_alloc)
 * 
 * \param[in]	arbre	Sous arbre dans lequel on insert la valeur
 * \param[in]	val		Valeur inséré dans l'arbre
 */
template<typename TypeCle, typename TypeValeur>
void	ArbreAVL<TypeCle, TypeValeur>::_auxInsererAVL(Noeud *&arbre, const TypeCle cle, const TypeValeur &val)	throw(std::bad_alloc)
{
	if (arbre == 0)
	{
		arbre = new ArbreAVL::Noeud(cle, val);
		cpt++;
		return ;
	}
	if(arbre->cle > cle)
	{
		_auxInsererAVL(arbre->gauche, cle, val);
		if ((_hauteur(arbre->gauche) - _hauteur(arbre->droite)) == 2) 
		{
			if (arbre->gauche->valeur >= val)
				_zigZigGauche(arbre);
			else
				_zigZagGauche(arbre);
		} 
		else
			arbre->hauteur = 1 + _maximum(_hauteur(arbre->gauche), _hauteur(arbre->droite));
	}
	else
	{
		_auxInsererAVL(arbre->droite, cle, val);
		if ((_hauteur(arbre->droite) - _hauteur(arbre->gauche)) == 2) 
		{
			if (arbre->droite->valeur <= val) //= pour le cas d'un doublon
				_zigZigDroit(arbre);
			else
				_zigZagDroit(arbre);
		} 
		else
			arbre->hauteur = 1 + _maximum(_hauteur(arbre->droite), _hauteur(arbre->gauche));
	}
}

/** \fn int Arbre<E>:: _hauteur(Noeud *arb) const
 *
 * \param[in] arb L'adresse du noeud dont on désire sa hauteur
 *
 * \return La hauteur de arb
 * 
 */
template <typename TypeCle, typename TypeValeur>
int ArbreAVL<TypeCle, TypeValeur>::_hauteur(Noeud *arb) const
{
	if (arb == 0)
		return -1;
	return arb->hauteur;
}

/**
 * \fn typename Arbre<E>:: Noeud* Arbre<E>:: _auxAppartient(Noeud* arbre, const E &data) const
 *
 * \param[in] arbre Le sous-arbre dans lequel on effectue la recherche
 * \param[in] data L'élément recherché dans le sous-arbre
 * \return L'adresse du noeud contenant data, NULL si data ne fait pas partie de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
typename ArbreAVL<TypeCle, TypeValeur>::Noeud* ArbreAVL<TypeCle, TypeValeur>::_auxAppartient(Noeud* src, const TypeCle &cle, const TypeValeur &val) const
{	
	if (src == NULL)
		return NULL;
	if (src->valeur == valeur && src->cle == cle)
		return src;
	if (src->valeur > val)
		return _auxAppartient(src->gauche, cle, val);
	else
		return _auxAppartient(src->droite, cle, val);
}

/**
 * \fn	void ArbreAVL<TypeCle, TypeValeur>::_zigZigGauche(ArbreAVL<TypeCle, TypeValeur>::Noeud * &K2)
 * \param[in, out]	K2	Le noeud critique
 */
template<typename TypeCle, typename TypeValeur>
void ArbreAVL<TypeCle, TypeValeur>::_zigZigGauche(ArbreAVL<TypeCle, TypeValeur>::Noeud * &K2)
{
	Noeud *K1;

	K1 = K2->gauche;
	K2->gauche = K1->droite;
	K1->droite = K2;
	K2->hauteur = 1 + _maximum(_hauteur(K2->gauche), _hauteur(K2->droite));
	K1->hauteur = 1 + _maximum(_hauteur(K1->gauche), K2->hauteur);

	K2 = K1;
}

/**
 * \fn	void ArbreAVL<TypeCle, TypeValeur>::_zigZigDroit(ArbreAVL<TypeCle, TypeValeur>::Noeud * &K2)
 * \param[in, out] K2 Le noeud critique
 */
template<typename TypeCle, typename TypeValeur>
void ArbreAVL<TypeCle, TypeValeur>::_zigZigDroit(ArbreAVL<TypeCle, TypeValeur>::Noeud * &K2)
{
	Noeud *K1;

	K1 = K2->droite;
	K2->droite = K1->gauche;
	K1->gauche = K2;
	K2->hauteur = 1 + _maximum(_hauteur(K2->droite), _hauteur(K2->gauche));
	K1->hauteur = 1 + _maximum(_hauteur(K1->droite), K2->hauteur);
	K2 = K1;
}

/**
 * \fn	void ArbreAVL<TypeCle, TypeValeur>::_zigZagGauche(ArbreAVL<TypeCle, TypeValeur>::Noeud *&K3)
 *
 * \param[in, out] K3 Le noeud critique
 * 
 */
template<typename TypeCle, typename TypeValeur>
void ArbreAVL<TypeCle, TypeValeur>::_zigZagGauche(ArbreAVL<TypeCle, TypeValeur>::Noeud *&K3)
{
	_zigZigDroit(K3->gauche);
	_zigZigGauche(K3);
}

/**
 * \fn	void ArbreAVL<TypeCle, TypeValeur>::_zigZagDroit(ArbreAVL<TypeCle, TypeValeur>::Noeud *& K3)
 *
 * \param[in, out] K3 Le noeud critique
 * 
 */
template<typename TypeCle, typename TypeValeur>
void ArbreAVL<TypeCle, TypeValeur>::_zigZagDroit(ArbreAVL<TypeCle, TypeValeur>::Noeud *& K3)
{
	_zigZigGauche(K3->droite);
	_zigZigDroit(K3);
}

/**
 * \fn int ArbreAVL<TypeCle, TypeValeur>::_maximum(int ent1, int ent2) const
 *
 * \param[in] ent1 Le premier entier à comparer
 * \param[in] ent2 Le second entier à comparer
 *
 * \return Le maximum entre ent1 et ent2
 * 
 */
template<typename TypeCle, typename TypeValeur>
int ArbreAVL<TypeCle, TypeValeur>::_maximum(int ent1, int ent2) const
{
	if (ent1 <= ent2)
		return ent2;
	else
		return ent1;
}

template<typename TypeCle, typename TypeValeur>
void  ArbreAVL<TypeCle, TypeValeur>::_auxCopier(Noeud *source, Noeud *&destination) throw(std::bad_alloc)
{
	if (source!=0)
	{
		destination = new Noeud(source->cle, source->valeur);
		_auxCopier(source->gauche, destination->gauche);
		_auxCopier(source->droite, destination->droite);
		destination->hauteur = source->hauteur;
	}
	else
		destination = NULL;
}

/**
 * \fn	void	ArbreAVL<TypeCle, TypeValeur>::_auxEnleverAVL(Noeud * & t, const TypeCle & cle)  
 *
 * \param[in] arbre Le sous-arbre dans lequel on effectue la recherche
 * \param[in] data L'élément recherché dans le sous-arbre
 * \return L'adresse du noeud contenant data, NULL si data ne fait pas partie de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
void	ArbreAVL<TypeCle, TypeValeur>::_auxEnleverAVL(Noeud * & t, const TypeCle & cle)  
{
	Noeud *tmp = this->_auxAppartient(t, cle);
	if(t->cle >  tmp->cle)
	{
		_auxEnleverAVL(t->gauche, cle);
		if ((_hauteur(t->gauche) - _hauteur(t->droite)) == 2) 
		{
			if (t->gauche->valeur > tmp->valeur)
				_zigZigGauche(t);
			else
				_zigZagGauche(t);
		} 
		else
			t->hauteur = 1 + _maximum(_hauteur(t->gauche), _hauteur(t->droite));
	}
	else if(t->valeur < tmp->valeur)
	{
		_auxEnleverAVL( t->droite, cle);
		if ((_hauteur(t->droite) - _hauteur(t->gauche)) == 2) 
		{
			if ( t->droite->valeur <= tmp->valeur) //= pour le cas d'un doublon
				_zigZigDroit(t);
			else
				_zigZagDroit(t);
		} 
		else
			t->hauteur = 1 + _maximum(_hauteur(t->droite), _hauteur(t->gauche));
	}
	else if( t->gauche != 0 && t->droite != 0 ) 
	{
		Noeud * temp = t->droite;
		while ( temp->gauche != 0)
			temp = temp->gauche;
		t->cle = temp->cle;
		t->valeur = temp->valeur;
		_auxRetireMin( t->droite );
	}
	else
	{
		Noeud * vieuxNoeud = t;
		t = ( t->gauche != 0 ) ? t->gauche : t->droite;  
		delete vieuxNoeud;  
		cpt--;
	}	
}

/**
 * \fn void ArbreAVL<TypeCle, TypeValeur>::_auxRetireMin( Noeud* & t) const throw(logic_error)
 *
 * \param[in] t Le sous-arbre dans lequel on fait l'enlèvement
 */
template<typename TypeCle, typename TypeValeur>
void ArbreAVL<TypeCle, TypeValeur>::_auxRetireMin( Noeud* & t) const throw(std::logic_error)
{
	if (t == 0)
		throw std::logic_error("_auxRetireMin: probleme pointeur NULL\n");
	else if (t->gauche != 0)
		_auxRetireMin( t->gauche );
	else
	{
		Noeud * tmp = t;
		t = t->droite;
		delete tmp;
	}
}

/**
 * \fn	typename ArbreAVL<TypeCle, TypeValeur>::Noeud   *ArbreAVL<TypeCle, TypeValeur>::_auxAppartient( Noeud* src, const TypeCle &data) const
 * \param[in]	src	Racine de l'arbre ou sous-arbre
 * \param[in]	cle	Clé recherché
 */
template<typename TypeCle, typename TypeValeur>
typename ArbreAVL<TypeCle, TypeValeur>::Noeud   *ArbreAVL<TypeCle, TypeValeur>::_auxAppartient( Noeud* src, const TypeCle &data) const
{       
	if (src == 0)
		return 0;
	if (src->cle == data)
		return src;
	if (src->cle > data)
		return _auxAppartient(src->gauche, data);
	else
		return _auxAppartient(src->droite, data);
}


/**
 * \fn	void    ArbreAVL<TypeCle, TypeValeur>::_auxEnOrdre(Noeud* arb, std::vector<std::pair<TypeCle, TypeValeur> >& v) const
 *
 * \param[in] arb Le sous-arbre à parcourir
 * \param[out] v Le vector qui contient le listage du sous-arbre
 */
template <typename TypeCle, typename TypeValeur>
void    ArbreAVL<TypeCle, TypeValeur>::_auxEnOrdre(Noeud* arb, std::vector<std::pair<TypeCle, TypeValeur> >& v) const
{       
	if (arb == 0)
		return;
	else
	{
		std::pair<TypeCle, TypeValeur>       tmp(arb->cle, arb->valeur);

		_auxEnOrdre(arb->gauche, v);
		v.push_back(tmp);
		_auxEnOrdre(arb->droite, v);
	}
}

/**
 * \fn	void    ArbreAVL<TypeCle, TypeValeur>::_auxPreOrdre(Noeud* arb, std::vector<std::pair<TypeCle, TypeValeur> >& v) const
 *
 * \param[in] arb Le sous-arbre à parcourir
 * \param[out] v Le vector qui contient le listage du sous-arbre
 */
template <typename TypeCle, typename TypeValeur>
void    ArbreAVL<TypeCle, TypeValeur>::_auxPreOrdre(Noeud* arb, std::vector<std::pair<TypeCle, TypeValeur> >& v) const
{       
	if (arb == 0)
		return;
	else
	{
		std::pair<TypeCle, TypeValeur>       tmp(arb->cle, arb->valeur);

		v.push_back(tmp);
		_auxPreOrdre(arb->gauche, v);
		_auxPreOrdre(arb->droite, v);
	}
}

/**
 * \fn	typename ArbreAVL<TypeCle, TypeValeur>::Noeud*      ArbreAVL<TypeCle, TypeValeur>:: _parent(Noeud* arb, Noeud *sArb) const throw(std::logic_error)
 */
template <typename TypeCle, typename TypeValeur>
typename ArbreAVL<TypeCle, TypeValeur>::Noeud*      ArbreAVL<TypeCle, TypeValeur>:: _parent(Noeud* arb, Noeud *sArb) const throw(std::logic_error)
{
	if (arb == 0)
		throw std::logic_error("parent: l'arbre est vide!\n");
	if (sArb == 0)
		throw std::logic_error("parent: l'element n'existe pas!\n");
	if (sArb == arb)
		throw std::logic_error("parent: Le parent de la racine n'existe pas!\n");
	if ( sArb->cle < arb->cle)
	{
		if (arb->gauche == sArb)
			return arb;
		else
			return _parent(arb->gauche, sArb);
	}
	else
	{
		if (arb->droite == sArb)
			return arb;
		else
			return _parent(arb->droite, sArb);
	}
}

/**
 * \fn	void    ArbreAVL<TypeCle, TypeValeur>::show()
 */
template<typename TypeCle, typename TypeValeur>
void    ArbreAVL<TypeCle, TypeValeur>::show()
{
	_show(this->racine);
}

/**
 * \fn	void    ArbreAVL<TypeCle, TypeValeur>::_show(ArbreAVL<TypeCle, TypeValeur>::Noeud *tmp)
 * \param[in]	tmp	Sous arbre à parcourir
 */
template<typename TypeCle, typename TypeValeur>
void    ArbreAVL<TypeCle, TypeValeur>::_show(ArbreAVL<TypeCle, TypeValeur>::Noeud *tmp)
{
	if (tmp == NULL)
		return;
	_show(tmp->gauche);
	if (tmp == this->racine)
		std::cout << "Racine: ";
	std::cout << "Cle: " << tmp->cle << " | Valeur: " << tmp->valeur <<  std::endl;
	if (tmp->gauche != NULL)
		std::cout << "Cle de l'element de gauche: " << tmp->gauche->cle << " | Valeur de l'element de gauche: " << tmp->gauche->valeur <<  std::endl;
	else
		std::cout << "Element de gauche = NULL" << std::endl;
	if (tmp->droite != NULL)
		std::cout << "Cle de l'element de droite: " << tmp->droite->cle << " | Valeur de l'element de droite: " << tmp->droite->valeur <<  std::endl;
	else
		std::cout << "Element de doite = NULL" << std::endl;
	_show(tmp->droite);
}

/**
 * \fn	std::pair<TypeCle, TypeValeur>	ArbreAVL<TypeCle, TypeValeur>::_successeur(Noeud* arb, const TypeCle & cle) throw (std::logic_error)
 * \param[in]	cle	Clé de l'élément dont on cherche le successeur
 * 
 * \return	La pair contenant la clé et la valeur du successeur
 */
template<typename TypeCle, typename TypeValeur>
std::pair<TypeCle, TypeValeur>	ArbreAVL<TypeCle, TypeValeur>::_successeur(Noeud* arb, const TypeCle & cle) throw (std::logic_error)
{
	if (this->cpt == 0)
		throw std::logic_error("successeur: l'arbre est vide!\n");
	Noeud* sArb = _auxAppartient(this->racine, cle);
	if (sArb == 0)
		throw std::logic_error("successeur: l'element n'existe pas!\n");
	if (cle == _max(arb))
		throw std::logic_error("successeur: l'element est le max dans l'arbre!\n");
	if (sArb->droite != 0)
	{
		TypeCle	tmpCle	= _min(sArb->droite);
		TypeValeur tmpValeur = valeur(tmpCle);
		std::pair<TypeCle, TypeValeur>	tmp(tmpCle, tmpValeur);
		return (tmp);
	}
	else
	{
		Noeud * pere = _parent(arb, sArb);
		while (pere->cle < sArb->cle)
			pere = _parent(arb,pere);
		std::pair<TypeCle, TypeValeur>	tmp(pere->cle, pere->valeur);
		return (tmp);
	}
}

/**
 * \fn	TypeCle	ArbreAVL<TypeCle, TypeValeur>::_max(Noeud *arb) const
 * \param[in]	arb	Sous arbre à parcourir
 * 
 * \return	La clé du max de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
TypeCle	ArbreAVL<TypeCle, TypeValeur>::_max(Noeud *arb) const
{
	if (arb->droite)
		_max(arb->droite);
	else
	{
		if (arb->gauche)
			_max(arb->gauche);
	}
	return (arb->cle);	
}

/**
 * \fn	TypeCle	ArbreAVL<TypeCle, TypeValeur>::_min(Noeud *arb) const
 * \param[in]	arb	Sous arbre à parcourir
 * 
 * \return	La clé du min de l'arbre
 */
template<typename TypeCle, typename TypeValeur>
TypeCle	ArbreAVL<TypeCle, TypeValeur>::_min(Noeud *arb) const
{
	if (arb->gauche)
		_max(arb->gauche);
	else
	{
		if (arb->droite)
			_max(arb->droite);
	}
	return (arb->cle);	
}

/**
 * \fn	bool    ArbreAVL<TypeCle, TypeValeur>::Noeud::operator==(Noeud *b)
 * \param[in]	b	Noeud à comparer
 * 
 * \return	Vrai si le noeud est identique, sinon faux
 */
template<typename TypeCle, typename TypeValeur>
bool    ArbreAVL<TypeCle, TypeValeur>::Noeud::operator==(Noeud *b)
{
	if (this->cle != b->cle || this->valeur != b->valeur || this->hauteur != b->hauteur)
		return false;
	if (this->gauche != NULL && b->gauche != NULL && this->gauche->operator ==(b->gauche) == false)
		return false;
	if (this->droite != NULL && b->droite != NULL && this->droite->operator ==(b->droite) == false)
		return false;
	return true;
}
